package com.c2b.algorithm.leetcode.base.monotone_stack;

import com.c2b.algorithm.leetcode.base.Printer;

import java.util.ArrayDeque;
import java.util.Arrays;
import java.util.Deque;

/**
 * <a href="https://leetcode.cn/problems/next-greater-element-iv/">下一个更大元素 IV(Next Greater Element IV)</a>
 * <p>给你一个下标从 0 开始的非负整数数组 nums 。对于 nums 中每一个整数，你必须找到对应元素的 第二大 整数。</p>
 * <p>
 * 如果 nums[j] 满足以下条件，那么我们称它为 nums[i] 的 第二大 整数：
 *     <ul>
 *         <li>j > i</li>
 *         <li>nums[j] > nums[i]</li>
 *         <li>恰好存在 一个 k 满足 i < k < j 且 nums[k] > nums[i] 。</li>
 *         <li>如果不存在 nums[j] ，那么第二大整数为 -1 。</li>
 *         <li>比方说，数组 [1, 2, 4, 3] 中，1 的第二大整数是 4 ，2 的第二大整数是 3 ，3 和 4 的第二大整数是 -1 。</li>
 *     </ul>
 *     请你返回一个整数数组 answer ，其中 answer[i]是 nums[i] 的第二大整数。
 * </p>
 * <p>
 * <b>示例：</b>
 * <pre>
 * 示例 1：
 *      输入：nums = [2,4,0,9,6]
 *      输出：[9,6,6,-1,-1]
 *      解释：
 *          下标为 0 处：2 的右边，4 是大于 2 的第一个整数，9 是第二个大于 2 的整数。
 *          下标为 1 处：4 的右边，9 是大于 4 的第一个整数，6 是第二个大于 4 的整数。
 *          下标为 2 处：0 的右边，9 是大于 0 的第一个整数，6 是第二个大于 0 的整数。
 *          下标为 3 处：右边不存在大于 9 的整数，所以第二大整数为 -1 。
 *          下标为 4 处：右边不存在大于 6 的整数，所以第二大整数为 -1 。
 *          所以我们返回 [9,6,6,-1,-1] 。
 *
 * 示例 2：
 *      输入：nums = [3,3]
 *      输出：[-1,-1]
 *      解释：
 *          由于每个数右边都没有更大的数，所以我们返回 [-1,-1] 。
 * </pre>
 * </p>
 * <p>
 * <b>提示：</b>
 * <ul>
 * <li>1 <= nums.length <= 10^5</li>
 * <li>-0 <= nums[i] <= 10^9</li>
 * </ul>
 * </p>
 *
 * @author c2b
 * @since 2023/11/6 15:50
 */
public class LC2454NextGreaterElement_IV_H {

    static class Solution {
        public int[] secondGreaterElement(int[] nums) {
            int[] ans = new int[nums.length];
            Arrays.fill(ans, -1);
            // int[]：
            // 0号位置：当前数在nums中的下标；
            // 1号位置：还需找到几个比当前数大的数，默认为2
            Deque<int[]> stack = new ArrayDeque<>();
            for (int currIndex = 0; currIndex < nums.length; currIndex++) {
                int currNum = nums[currIndex];
                Deque<int[]> tempStack = new ArrayDeque<>();
                while (!stack.isEmpty() && currNum > nums[stack.peekLast()[0]]) {
                    int[] ints = stack.pollLast();
                    if (ints[1] == 1) {
                        ans[ints[0]] = currNum;
                    } else {
                        tempStack.offerLast(new int[]{ints[0], 1});
                    }
                }
                stack.offerLast(new int[]{currIndex, 2});
                while (!tempStack.isEmpty()) {
                    stack.offerLast(tempStack.pollLast());
                }
            }
            return ans;
        }
    }

    public static void main(String[] args) {
        Solution solution = new Solution();
        Printer.printArrayInt(solution.secondGreaterElement(new int[]{2, 4, 0, 9, 6}));
        Printer.printArrayInt(solution.secondGreaterElement(new int[]{3,3}));
    }
}
